lib/Mi manual de algoritmos/version_actual/src/grafos/puntos_articulacion.cpp

   1 // Complejidad: O(E + V)
   2
   3 typedef string node;
   4 typedef map<node, vector<node> > graph;
   5 typedef char color;
   6 const color WHITE = 0, GRAY = 1, BLACK = 2;
   7 graph g;
   8 map<node, color> colors;
   9 map<node, int> d, low;
  10
  11 set<node> cameras; //contendrá los puntos de articulación
  12 int timeCount;
  13
  14 // Uso: Para cada nodo u:
  15 // colors[u] = WHITE, g[u] = Aristas salientes de u.
  16 // Funciona para grafos no dirigidos.
  17
  18 void dfs(node v, bool isRoot = true){
  19   colors[v] = GRAY;
  20   d[v] = low[v] = ++timeCount;
  21   const vector<node> &neighbors = g[v];
  22   int count = 0;
  23   for (int i=0; i<neighbors.size(); ++i){
  24     if (colors[neighbors[i]] == WHITE){
  25       //(v, neighbors[i]) is a tree edge
  26       dfs(neighbors[i], false);
  27       if (!isRoot && low[neighbors[i]] >= d[v]){
  28         //current node is an articulation point
  29         cameras.insert(v);
  30       }
  31       low[v] = min(low[v], low[neighbors[i]]);
  32       ++count;
  33     }else{ // (v, neighbors[i]) is a back edge
  34       low[v] = min(low[v], d[neighbors[i]]);
  35     }
  36   }
  37   if (isRoot && count > 1){
  38     //Is root and has two neighbors in the DFS-tree
  39     cameras.insert(v);
  40   }
  41   colors[v] = BLACK;
  42 }
  43